<!DOCTYPE html>
<html>
	<head>
		<meta charset="utf-8">
		<title>图结构</title>
	</head>
	<body>
    <script src="./Dictionay.js" type="text/javascript" charset="utf-8"></script>
    <script src="./Queue.js" type="text/javascript" charset="utf-8"></script>
    <script type="text/javascript">
      function Graph() {
          // 属性
          this.vertexes = [] // 存储顶点
          this.adjList =  new Dictionay()// 存储边
          
          // 方法
          // 添加方法
          // 添加顶点
          // 添加方法
          Graph.prototype.addVertex = function (v) {
              this.vertexes.push(v)
              this.adjList.set(v, [])
          }
          // 添加边
          Graph.prototype.addEdge = function (v, w) {
              this.adjList.get(v).push(w)
              this.adjList.get(w).push(v)
          }
          
          //tostring方法
          Graph.prototype.toString = function () {
              let resultStr = ""
              for (let i = 0; i < this.vertexes.length; i++) {
                  resultStr += this.vertexes[i] + "->"
                  let adj = this.adjList.get(this.vertexes[i])
                  for (let j = 0; j < adj.length; j++) {
                      resultStr += adj[j] + " "
                  }
                  resultStr += "\n"
              }
              return resultStr
          }
          
          // 广度优先算法
/*          为了记录顶点是否被访问过, 我们使用三种颜色来反应它们的状态:(或者两种颜色也可以)
          白色: 表示该顶点还没有被访问.
          灰色: 表示该顶点被访问过, 但并未被探索过.
          黑色: 表示该顶点被访问过且被完全探索过. */
          // 初始化颜色代码
          Graph.prototype.initializeColor = function () {
              let colors = []
              for (let i = 0; i < this.vertexes.length; i++) {
                  colors[this.vertexes[i]] = "white"
              }
              return colors
          }
          
          Graph.prototype.bfs = function (v, handler) {
              // 1.初始化颜色
              let color = this.initializeColor()
          
              // 2.创建队列
              let queue = new Queue()
          
              // 3.将传入的顶点放入队列中
              queue.enqueue(v)
          
              // 4.从队列中依次取出和放入数据
              while (!queue.isEmpty()) {
                  // 4.1.从队列中取出数据
                  let qv = queue.dequeue()
          
                  // 4.2.获取qv相邻的所有顶点
                  let qAdj = this.adjList.get(qv)
          
                  // 4.3.将qv的颜色设置成灰色
                  color[qv] = "gray"
          
                  // 4.4.将qAdj的所有顶点依次压入队列中
                  for (let i = 0; i < qAdj.length; i++) {
                      let a = qAdj[i]
                      if (color[a] === "white") {
                          color[a] = "gray"
                          queue.enqueue(a)
                      }
                  }
          
                  // 4.5.因为qv已经探测完毕, 将qv设置成黑色
                  color[qv] = "black"
          
                  // 4.6.处理qv
                  if (handler) {
                      handler(qv)
                  }
              }
          }
          
          // 深度优先搜索
          Graph.prototype.dfs = function (handler) {
              // 1.初始化颜色
              let color = this.initializeColor()
          
              // 2.遍历所有的顶点, 开始访问
              for (let i = 0; i < this.vertexes.length; i++) {
                  if (color[this.vertexes[i]] === "white") {
                      this.dfsVisit(this.vertexes[i], color, handler)
                  }
              }
          }
          
          // dfs的递归调用方法
          Graph.prototype.dfsVisit = function (u, color, handler) {
              // 1.将u的颜色设置为灰色
              color[u] = "gray"
          
              // 2.处理u顶点
              if (handler) {
                  handler(u)
              }
          
              // 3.u的所有邻接顶点的访问
              let uAdj = this.adjList.get(u)
              for (let i = 0; i < uAdj.length; i++) {
                  let w = uAdj[i]
                  if (color[w] === "white") {
                      this.dfsVisit(w, color, handler)
                  }
              }
          
              // 4.将u设置为黑色
              color[u] = "black"
          }
      }
      
      // 测试代码
      let graph = new Graph()
      
      // 添加顶点
      let myVertexes = ["A", "B", "C", "D", "E", "F", "G", "H", "I"]
      for (let i = 0; i < myVertexes.length; i++) {
          graph.addVertex(myVertexes[i])
      }
      
      // 添加边
      graph.addEdge('A', 'B');
      graph.addEdge('A', 'C');
      graph.addEdge('A', 'D');
      graph.addEdge('C', 'D');
      graph.addEdge('C', 'G');
      graph.addEdge('D', 'G');
      graph.addEdge('D', 'H');
      graph.addEdge('B', 'E');
      graph.addEdge('B', 'F');
      graph.addEdge('E', 'I');
      
      // 调用广度优先算法
      let resultBfs = ""
      graph.bfs(graph.vertexes[0], function (v) {
          resultBfs += v + " "
      })
      alert(resultBfs) // A B C D E F G H I 
      
      // 调用深度优先算法
      let resultDfs = ""
      graph.dfs(function (v) {
          resultDfs += v + " "
      })
      alert(resultDfs) // A B C D E F G H I 
    </script>
	</body>
</html>
